#include "string_array.h"
#include <malloc.h>
using namespace std;

void myStr::print() {
    for (int i = 0; i < this->length; i++)
        cout << this->data[i];
    cout << endl;
}

void myStr::printNext() {
    for (int i = 0; i < length; i++)
        cout << next[i] + 1;
    cout << endl;
}

void myStr::printNextVal() {
    for (int i = 0; i < length; i++)
        cout << nextVal[i] + 1;
    cout << endl;
}

myStr::myStr(const char* a)
{
    data = (char*)malloc(sizeof(char) * 50);
    int i = 0;
    do
    {
        data[i] = a[i]; i++;
    } while (a[i] != '\0');
    length = i;
}
myStr::~myStr()
{
    delete data;
    delete next;
    delete nextVal;
}

int simpleMatch(const myStr& S, const myStr& T)
{
    for (int i = 0; i < S.length; i++)
    {
        if (S.data[i] == T.data[0])
        {
            for (int j = i; j < S.length && j < i + T.length; j++)
            {
                if (S.data[j] != T.data[j - i])break;
                if (j == i + T.length - 1)return i + 1;
            }
        }
    }
    return -1;

}
int simpleMatch_index(const myStr& S, const myStr& T, int start)
{
    for (int i = start; i < S.length; i++)
    {
        if (S.data[i] == T.data[0])
        {
            for (int j = i; j < S.length && j < i + T.length; j++)
            {
                if (S.data[j] != T.data[j - i])break;
                if (j == i + T.length - 1)return i + 1;
            }
        }
    }
    return -1;
}

int kmpMatch(const myStr& S, const myStr& T)
{
    return simpleMatch(S, T);
}

bool replaceStr(myStr& S, const int& start, const myStr& T, const myStr& V)
{
    int head = simpleMatch_index(S, T, start);
    if (head == -1)return 0;
    head--;
    char end[50] = "!";
    for (int i = 0; head + T.length + i < S.length; i++)
    {
        end[i] = S.data[head + T.length + i];
    }
    S.length = S.length - T.length + V.length;
    for (int i = 0; i < V.length; i++, head++)
    {
        S.data[head] = V.data[i];
    }
    for (int i = 0; head < S.length + 1; head++, i++)
    {
        S.data[head] = end[i];
    }
    return 1;

}

void myStr::kmp_nextVal()
{
    nextVal = (int*)malloc(sizeof(int) * length);
    int j = 0, k = -1;
    nextVal[0] = -1;
    while (j < length - 1)
    {
        if (k == -1 || data[j] == data[k])
        {
            j++; k++;
            if (data[j] == data[k])
                nextVal[j] = nextVal[k];
            else
                nextVal[j] = k;
        }
        else k = nextVal[k];
    }
}

void myStr::kmp_next()
{
    next = (int*)malloc(sizeof(int) * length);
    int j = 0, k = -1;
    next[0] = -1;
    while (j < length - 1)
    {
        if (k == -1 || data[j] == data[k])
        {
            j++; k++;
            next[j] = k;
        }
        else k = next[k];
    }
}

void myMatrix::printMatrix() {
    cout << rowNum << "," << colNum << "," << nodeNum << endl;

    for (int i = 0; i < nodeNum; i++)
        cout << nodeList[i].row << "," << nodeList[i].col << "," << nodeList[i].value << endl;
}

myMatrix::myMatrix()
{

}
myMatrix::myMatrix(const int& rNum, const int& cNum, const int& nNum, const int* m)
{
    nodeList = (matrixNode*)malloc(nNum * sizeof(matrixNode));
    rowNum = rNum;
    colNum = cNum;
    nodeNum = nNum;
    int* a;
    a = new int[100];
    for (int k = 0; k < 3 * nNum; k++)
    {
        a[k] = m[k];
    }

    int i, j, temp_r, temp_c, temp_v;
    for (i = 0; i <= 3 * (nNum - 1); i += 3)
    {
        for (int j = 0; j < nNum - 1; j++)
        {
            if (a[3 * j] > a[3 * (j + 1)])
            {
                temp_r = a[3 * j];
                a[3 * j] = a[3 * j + 3];
                a[3 * j + 3] = temp_r;

                temp_c = a[3 * j + 1];
                a[3 * j + 1] = a[3 * j + 4];
                a[3 * j + 4] = temp_c;

                temp_v = a[3 * j + 2];
                a[3 * j + 2] = a[3 * j + 5];
                a[3 * j + 5] = temp_v;
            }
            else if (a[3 * j] == a[3 * j + 3] && a[3 * j + 1] > a[3 * j + 4])
            {
                temp_r = a[3 * j];
                a[3 * j] = a[3 * j + 3];
                a[3 * j + 3] = temp_r;

                temp_c = a[3 * j + 1];
                a[3 * j + 1] = a[3 * j + 4];
                a[3 * j + 4] = temp_c;

                temp_v = a[3 * j + 2];
                a[3 * j + 2] = a[3 * j + 5];
                a[3 * j + 5] = temp_v;

            }
        }
    }
    for (int i = 0; i < nNum; i++)
    {
        nodeList[i].row = a[i * 3];
        nodeList[i].col = a[i * 3 + 1];
        nodeList[i].value = a[i * 3 + 2];
    }


}

myMatrix::~myMatrix()
{
    free(nodeList);
}

void ::myMatrix::FastTransposeSMatrix(myMatrix& T)
{

    T.rowNum = colNum;
    T.colNum = rowNum;
    T.nodeNum = nodeNum;

    T.nodeList = new matrixNode[nodeNum + 1];

    int p, q, t, col;
    int* num;
    num = new int[100];
    int cpot[100];


    if (T.nodeNum)
    {
        for (col = 0; col < colNum; ++col)
            num[col] = 0;

        for (t = 0; t < nodeNum; ++t)
            ++num[nodeList[t].col];

        cpot[0] = 0;

        for (col = 1; col < colNum; ++col)
            cpot[col] = cpot[col - 1] + num[col - 1];

        for (p = 0; p < nodeNum; ++p) {
            col = nodeList[p].col;
            q = cpot[col];

            T.nodeList[q].row = nodeList[p].col;
            T.nodeList[q].col = nodeList[p].row;
            T.nodeList[q].value = nodeList[p].value;

            ++cpot[col];

        }
    }

    delete[]num;
}

//int main()
//{
//    myStr S("hello TJU!");
//    myStr T("TJU");
//    myStr T1("NKU");
//    myStr T2("future");
//
//    int isFind;
//    isFind = replaceStr(S, 8, T1, T2);
//    cout << isFind << endl;//0
//    isFind = replaceStr(S, 1, T, T2);
//    cout << isFind << endl;//1
//    S.print();//hello future!
//    isFind = replaceStr(S, 1, T1, T2);
//    cout << isFind << endl;//0
//
//    myStr matchS("aabaabaabaac");
//    myStr matchT("aabaac");
//
//    isFind = simpleMatch(matchS, matchT);
//    cout << isFind << endl;//7
//
//    matchS.kmp_next();
//    matchS.kmp_nextVal();
//    matchS.printNext();//012123456789
//    matchS.printNextVal();//002002002009
//
//    matchT.kmp_next();
//    matchT.kmp_nextVal();
//    matchT.printNext();//012123
//    matchT.printNextVal();//002003
//
//    isFind = kmpMatch(matchS, matchT);
//    cout << isFind << endl;//7
//
//    int i[] = { 2,3,10,2,4,30,4,4,25 };
//    myMatrix M(5, 6, 3, i);
//    M.printMatrix();//5,6,3
//                    //2,3,10
//                    //2,4,30
//                    //4,4,25
//    myMatrix TT;
//    M.FastTransposeSMatrix(TT);
//    TT.printMatrix();//6,5,3
//                    //3,2,10
//                    //4,2,30
//                    //4,4,25
//
//    return 0;
//}